package main

import (
	"fmt"
	"strconv"
)

/* 打表

由于输入范围很小，我们可以直接把所有结果计算出来（这一共有 $8\cdot 30=240$ 个）。

从小到大构造 $10$ 镜像数字，构造方法如下：

- 对于 [10^i,10^{i+1}) 范围内的每个数，将除了末尾数位的其余数位反转并拼到原数字末尾，这样可以得到所有长为 $2i+1$ 的 $10$ 镜像数字；
- 对于 [10^i,10^{i+1}) 范围内的每个数，将所有数位反转并拼到原数字末尾，这样可以得到所有长为 $2i+2$ 的 $10$ 镜像数字。

对每个 $10$ 镜像数字判断其是否为 $k=[2,9]$ 进制数字，当得到所有 $30$ 个 $k$ 进制数字时，结束打表。

注：这最多需要枚举到 $644545$（对应的 $10$ 镜像数字为 $64454545446$）

*/

func main() {
	const lim = 30
	const maxK = 9
	const doneMask = 1<<(maxK+1) - 1 ^ 3

	ans := [maxK + 1][]int{}
	done := 0

	check := func(s []byte) {
		num, _ := strconv.Atoi(string(s))
	next:
		for k := 2; k <= maxK; k++ {
			if done>>k&1 == 0 {
				t := strconv.FormatInt(int64(num), k)
				for i, n := 0, len(t); i < n/2; i++ { // 判断 num 是否为 k 进制数字
					if t[i] != t[n-1-i] {
						continue next
					}
				}
				ans[k] = append(ans[k], num)
				if len(ans[k]) == lim {
					done |= 1 << k
				}
			}
		}
	}

	for base := 1; done != doneMask; base *= 10 {
		for i := base; i < base*10 && done != doneMask; i++ {
			s := []byte(strconv.Itoa(i))
			n := len(s)
			for j := n - 2; j >= 0; j-- {
				s = append(s, s[j])
			}
			check(s)
		}
		for i := base; i < base*10 && done != doneMask; i++ {
			s := []byte(strconv.Itoa(i))
			n := len(s)
			for j := n - 1; j >= 0; j-- {
				s = append(s, s[j])
			}
			check(s)
		}
	}

	for k := 2; k <= maxK; k++ {
		for i := 1; i < lim; i++ {
			ans[k][i] += ans[k][i-1] // 计算前缀和
		}
		fmt.Printf("%#v,\n", ans[k])
	}
}

// github.com/EndlessCheng/codeforces-go
var ans = [10][30]int64{
	{},
	{},
	{1, 4, 9, 16, 25, 58, 157, 470, 1055, 1772, 9219, 18228, 33579, 65802, 105795, 159030, 212865, 286602, 872187, 2630758, 4565149, 6544940, 9674153, 14745858, 20005383, 25846868, 39347399, 759196316, 1669569335, 2609044274},
	{1, 3, 7, 15, 136, 287, 499, 741, 1225, 1881, 2638, 31730, 80614, 155261, 230718, 306985, 399914, 493653, 1342501, 2863752, 5849644, 9871848, 14090972, 18342496, 22630320, 28367695, 36243482, 44192979, 71904751, 155059889},
	{1, 3, 6, 11, 66, 439, 832, 1498, 2285, 3224, 11221, 64456, 119711, 175366, 233041, 739646, 2540727, 4755849, 8582132, 12448815, 17500320, 22726545, 27986070, 33283995, 38898160, 44577925, 98400760, 721411086, 1676067545, 53393239260},
	{1, 3, 6, 10, 16, 104, 356, 638, 1264, 1940, 3161, 18912, 37793, 10125794, 20526195, 48237967, 78560270, 126193944, 192171900, 1000828708, 1832161846, 2664029984, 3500161622, 4336343260, 6849225412, 9446112364, 12339666346, 19101218022, 31215959143, 43401017264},
	{1, 3, 6, 10, 15, 22, 77, 188, 329, 520, 863, 1297, 2074, 2942, 4383, 12050, 19827, 41849, 81742, 156389, 325250, 1134058, 2043967, 3911648, 7009551, 11241875, 15507499, 19806423, 24322577, 28888231},
	{1, 3, 6, 10, 15, 21, 29, 150, 321, 563, 855, 17416, 83072, 2220384, 6822448, 13420404, 20379000, 29849749, 91104965, 321578997, 788407661, 1273902245, 1912731081, 2570225837, 3428700695, 29128200347, 69258903451, 115121130305, 176576075721, 241030621167},
	{1, 3, 6, 10, 15, 21, 28, 37, 158, 450, 783, 1156, 1570, 2155, 5818, 14596, 27727, 41058, 67520, 94182, 124285, 154588, 362290, 991116, 1651182, 3148123, 5083514, 7054305, 11253219, 66619574},
	{1, 3, 6, 10, 15, 21, 28, 36, 227, 509, 882, 1346, 1901, 2547, 3203, 10089, 35841, 63313, 105637, 156242, 782868, 2323319, 4036490, 5757761, 7586042, 9463823, 11349704, 13750746, 16185088, 18627530},
}

func kMirror(k, n int) int64 {
	return ans[k][n-1]
}
